#define _CRT_SECURE_NO_WARNINGS 1

/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
class Solution {
public:
	void _Convert(TreeNode* root, TreeNode*& last)
	{
		if (root == nullptr)
			return;

		_Convert(root->left, last);
		last->right = root;
		root->left = last;
		last = root;
		_Convert(root->right, last);
	}
	TreeNode* Convert(TreeNode* pRootOfTree) {
		if (pRootOfTree == nullptr) return nullptr;
		TreeNode* head = new TreeNode(0);
		TreeNode* ret = head;
		head->left = head;
		head->right = head;
		_Convert(pRootOfTree, head);
		ret->right->left = nullptr;

		return ret->right;
	}
};
